#include<bits/stdc++.h>

using namespace std;
using ll = long long;
#define endl '\n'
struct Node {
    int x, y;

};

const int maxn = 101;
int a[maxn][maxn];
int book[maxn][maxn];
int fx[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};//四连通 顺时针方向
int n, m;
int sx, sy, ex, ey;

int dp[maxn][maxn];
Node pre[maxn][maxn];//打印最短路径，指向父（前一个）结点
/**
 * 输出源点从源点开始s(sx,sy) 形成的bfs树，pre[i][j]存储的是g[i][j]的父节点
 * @param sx  源点的横坐标
 * @param sy  源点的纵坐标
 * @return
 */

int bfs(int x, int y) {
    int cnt = 0;
    queue<Node> Q;
    Q.push({x, y});
    book[x][y] = 1;
    dp[x][y] = 0;//
    while (Q.size()) {
        Node head = Q.front();
        int k = dp[head.x][head.y];//队列头P结点距离源点为k
        for (int i = 0; i < 4; i++) {
            int nx = head.x + fx[i][0];
            int ny = head.y + fx[i][1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || book[nx][ny] == 1 || a[nx][ny] == 1)continue;
            Q.push({nx, ny});
            book[nx][ny] = 1;
            dp[nx][ny] = k + 1;//P扩张的点都是k+1
            pre[nx][ny].x = head.x;
            pre[nx][ny].y = head.y;
        }
        Q.pop();
        ++cnt;
    }
    return cnt;
}


int main() {
    freopen("A.in", "r", stdin);
    n = 5;
    m = 5;
    memset(a, 0, sizeof(a));
    memset(book, 0, sizeof(book));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    sx = 0;
    sy = 0;
    ex = n - 1;
    ey = m - 1;
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            pre[i][j].x = -1;
            pre[i][j].y = -1;
        }
    dp[ex][ey] = 0;
    bfs(ex, ey);
    int x = sx, y = sy;
    while (1) {
        cout << "(" << x << "," << y << ")" << endl;
        int nx = pre[x][y].x;
        int ny = pre[x][y].y;
        if (nx == -1 && ny == -1)break;
        x = nx;
        y = ny;
    }


    return 0;
}
